package com.practice.search;

import com.practice.util.FileHelper;

public class WordRectangle {
	private final static String DIR = "src/test/resources/com/practice/search";
	
	private Trie				root;
	private char[][] 			solution;
	private Trie[][] 			trie;
	private int					N;

	public static void main(String[] args) {
		WordRectangle w = new WordRectangle();
		long t0 = System.currentTimeMillis();
		w.find(7);
		long t1 = System.currentTimeMillis();
		System.out.println("Time = " + (t1-t0));
	}

	public void find(int n) {
		N = n;
		root = new Trie();
		String[] words = readWords(N);
		
		for (String word : words) {
			root.addWord(word);
		}
		root.processKeySet();
		
		solution = new char[N][N];
		trie = new Trie[N][N];
		for (String word : words) {
			solution[0] = word.toCharArray();
			for (int i=0; i<N; i++) trie[0][i] = root.getNode(solution[0][i]);
			
			if (search(root, 1, 0)) {
				print();
				return;
			}
		}
	}
	
	private boolean search(Trie h, int i, int j) {
		if (i == N) return true;
		if (j == N) return search(root, i+1, 0);
		for (char c : trie[i-1][j].keySet()) {
			Trie hNext = h.getNode(c);
			if (hNext != null) {
				solution[i][j] = c;
				if (j == 0 && stopSearch(i)) break;
				trie[i][j] = trie[i-1][j].getNode(c);
				if (search(hNext, i, j+1)) return true;
			}
		}
		return false;
	}
	
	private boolean stopSearch(int current) {
		for (int i=1; i<=current; i++) {
			if (solution[i][0] < solution[0][i]) return false;
		}
		return solution[current][0] > solution[0][current];
	}
	
	// ------------------------------------------------------------------------
	// Facilities
	// ------------------------------------------------------------------------
	
	private void print() {
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) System.out.print(solution[i][j] + " ");
			System.out.println();
		}
	}
	
	private String[] readWords(int N) {
		String content = FileHelper.readFile(DIR + "/WORD" + N + ".LST");
		return content.split("\n");
	}
}
